/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-10-12
 * Time: 19:19
 */
public class test3 {
    /*
    三步问题：有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
    对1e9+7进行模运算，加一次就模一次
    动态规划（斐波那契问题）
     */

    public int waysToStep(int n) {
        if(n==1||n==2){
            return n;
        }
        if(n==3){
            return 4;
        }
        int MOD = (int ) 1e9+7;
        int [] dp = new int [n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){
            dp[i]=((dp[i-1]+dp[i-2])%MOD + dp[i-3])%MOD;
        }
        return dp[n];
    }
}
